home *** CD-ROM | disk | FTP | other *** search
/ SGI Hot Mix 17 / Hot Mix 17.iso / HM17_SGI / research / lib / obsolete / maketree.pro < prev    next >
Text File  |  1997-07-08  |  8KB  |  298 lines
  1. ; $Id: maketree.pro,v 1.2 1997/01/15 04:02:19 ali Exp $
  2. ;
  3. ;  Copyright (c) 1993-1997, Research Systems Inc.  All rights
  4. ;  reserved. Unauthorized reproduction prohibited.
  5.  
  6. pro Adjust, sim, imin, N
  7. for i = N-1,2*N do  $
  8.   if Sim(i) ge Sim(imin(i)) - 1 THEN   $
  9.      Sim(imin(i)) = Sim(i) + 2
  10. return
  11. end
  12.  
  13.  pro PutV,X,V
  14.     
  15.  if V(0) EQ -1 THEN V=[X]      $
  16.     ELSE V = [X,V]
  17.  RETURN
  18.  END         ;PutV
  19.  
  20.  pro RemoveV,V
  21.  
  22.  if (N_Elements(V) GT 1) THEN V = V(1:*)         $
  23.  ELSE V=-1
  24.  
  25.  RETURN
  26.  END
  27.    
  28.  Pro maketree,pos,Imin,Sim,unit,CaseName=CasName, Width = LS
  29. ;+
  30. ; NAME: 
  31. ;    MAKETREE
  32. ;
  33. ; PURPOSE:
  34. ;    MakeTree constructs a tree representation of the nested clusters
  35. ;    created by the join procedure. 
  36. ;
  37. ; CATEGORY:
  38. ;    Statistics.
  39. ;
  40. ; CALLING SEQUENCE:
  41. ;    MAKETREE, Pos, Imin, Sim [, Unit]
  42. ;
  43. ; INPUT:
  44. ;    Pos(i):    The position of the ith case as a leaf in the tree to be 
  45. ;        constructed.
  46. ;
  47. ;      Imin(i):    The smallest cluster to strictly contain the case or object i.
  48. ;
  49. ;      Sim (i):    A measure of similarity among the objects in cluster i.
  50. ;
  51. ; OPTIONAL INPUT PARAMETERS:
  52. ;    Unit:    The file unit for output.  Default is to the screen.
  53. ;
  54. ; KEYWORDS:
  55. ;    WIDTH:    User-supplied tree width in characters.  The default is 60.
  56. ;        MAKETREE tries to fit the tree into the specified width.
  57. ;
  58. ;     CASENAME:    User-supplied vector of case names to be used in the output.
  59. ;         
  60. ;
  61. ; PROCEDURE:
  62. ;    We scan the cases in the order they appear in the tree.
  63. ;    A list V is maintained of strictly increasing clusters to be
  64. ;    used to determine which cluster should appear in the gap 
  65. ;    between case i and case i+1.  Each cluster in V contains at
  66. ;    least one case that has been scanned. 
  67. ;-
  68.  
  69.  if(N_elements(unit) EQ 0) THEN unit =-1 
  70.    
  71.  
  72.  N=N_Elements(pos)         ; N= # of cases
  73.  M= 2*N-2                  ; M = Last cluster
  74.  NC=size(CasName)
  75.  
  76. mx=max(Sim)
  77. Sim(M+1) = mx; assign length to final branch from
  78.                          ; largest cluster
  79.  
  80.  
  81.  if N_Elements(LS) EQ 0 THEN LS = 60 
  82.  if (NC(0) NE 0 ) THEN BEGIN   
  83.                              ;check and, maybe, fix case names
  84.    CaseName=CasName
  85.    if (NC(1) LT N) THEN BEGIN
  86.      printf,unit,'kmeans-missing Case names'
  87.      I=Indgen(N)
  88.      CaseName=[CaseName,'Case'+STRTRIM(I(NC(1):N-1),2.)]
  89.    ENDIF
  90.  ENDIF ELSE CaseName= 'Case'+STRTRim(INDgen(N),2)
  91.  
  92.  
  93.  Visited=Intarr(M+1)   ; Visited(i)=0,if cluster i is not in V
  94.                        ;           =1, if in list and has one
  95.                        ;                branch
  96.                        ;           =-1,if in list but no
  97.                        ;                 branches
  98.                     
  99.  
  100.  
  101. P=INtarr(N)
  102. P(Pos)=INDGEN(N)         ; P(i)= ith case in tree
  103. ;Sim(0) = Sim(2*N)
  104. If(N_ELEMENTS(unit) EQ 0) THEN unit = -1
  105.  
  106. ;if N_ELEMENTS(RL) EQ 0 THEN BEGIN
  107.   mn = min(Sim)
  108.   Sim1=Fix((Sim-mn) *((LS-3)/(mx-mn)))+1
  109. ; ENDIF ELSE BEGIN
  110. ;  sim1 = sim
  111. ;  Sim1(sort(sim)) = (INDGEN(2*N) + LS -2*N)>1
  112.  ;ENDELSE
  113.  
  114.  Adjust, Sim1, Imin, N-1        ;add length to branches where needed
  115.                          ;because of closeness.
  116. Sim1(0) = Sim1(2*N-2) + 2
  117.  
  118.  Gap=INTarr(N)           ; Gap(i)= Cluster # between i and i+1
  119.  
  120.  
  121.  
  122.  for i = 1l,N-1 DO BEGIN    ; Make Gap
  123.      Here=Imin(P(i-1)) 
  124.                      ; Here = smallest cluster containing P(i)
  125.  
  126.      if (i EQ 1 ) THEN BEGIN  ;Try to put first 3 smallest
  127.                               ;clusters containing i on V
  128.         V=[HERE,IMIN(HERE)]
  129.         Visited(HERE)=1
  130.         Visited(Imin(HERE))=1
  131.         Gap(1)=IMin(HERE)              ;second smallest in gap
  132.         if(i LT N-1) THEN BEGIN
  133.            V=[V,IMin(IMin(HERE))]
  134.            Visited(Imin(Imin(here)))=-1
  135.                 
  136.         ENDIf
  137.     ENDIF ELSE BEGIN
  138.  
  139.  
  140.  
  141.  
  142.           CASE Visited(HERE) OF
  143.  
  144.  
  145.  
  146.  
  147.           1:BEGIN                ;smallest containing cluster 
  148.                                         ; has first branch
  149.  
  150.  
  151.             ;V=V(1:*)            ;remove it from list 
  152.             RemoveV,V
  153.             Gap(i)= V(0)         ;make sur parent has a
  154.                                  ; branch before closing
  155.  
  156. if Visited(Gap(i)) and N_elements(V) GT 1 THEN BEGIN
  157.                          ; To assure closure of large cluster
  158.                Gap(i) =V(1)
  159.                Off = V(0)
  160.                V=V(1:*)
  161.              ENDIF else OFF=-1
  162.  
  163.  
  164.  
  165.             Case Visited(Gap(i)) OF
  166.  
  167.             1:BEGIN
  168.                GI=IMIN(Gap(i))
  169.  
  170.                     if(Visited(GI) EQ -1) THEN Gap(i)=GI  $
  171.                     ELSE RemoveV,V 
  172.  
  173.                    if(i LE N-2) THEN BEGIN
  174.                     GI=IMIN(Gap(i))
  175.  
  176.                    if (Visited(GI) EQ 0) THEN BEGIN
  177.                     if Visited(Gap(i)) EQ -1 THEN BEGIN
  178.                       if(N_Elements(V) GE 3) THEN      $
  179.                             V=[V(0:1),GI,V(2:*)]    $
  180.                       ELSE IF V(0) NE -1 THEN V=[V,GI]    $
  181.                            ELSE V= [GI]
  182.                     ENDIF ELSE if N_Elements(V) EQ 0      $
  183.                                 THEN V=[GI] ELSE V=[GI,V]
  184.                     Visited(GI)=-1
  185.                   ENDIF
  186.                ENDIF
  187.              END
  188.  
  189.             ELSE :  BEGIN
  190.                     
  191.                     if(i LE N-2) THEN BEGIN
  192.                       GI=IMIN(Gap(i))
  193.                       if (Visited(GI) EQ 0) THEN BEGIN
  194.                        if N_Elements(V) EQ 1 THEN     $
  195.                          V=[V(0),GI] ELSE V=[V(0),GI,V(1:*)]
  196.                        Visited(GI)=-1
  197.                       ENDIF
  198.                     ENDIF
  199.                    END
  200.  
  201.         ENDCASE
  202.  
  203.         Visited(Gap(i))=1
  204.         if Off NE -1 THEN PutV,OFF,V            
  205.         END                            ;Case Visited(Here)=1
  206.  
  207.  
  208.           ELSE:BEGIN 
  209.                Gap(i)=IMIN(HERE)
  210.                if Gap(i) eq Gap(i-1) THEN BEGIN
  211.                  Gap(i) = IMIN (Gap(i))
  212.                endif
  213.            
  214.               Visited(Here)=1
  215.  
  216.               if Visited(Gap(i)) EQ 1 and N_elements(V) GT 1 $
  217.                THEN  V=V(1:*)
  218.               if(i LE N-2) THEN BEGIN
  219.                  GI=IMIN(Gap(i))
  220.                  if (Visited(GI) EQ 0) THEN BEGIN
  221.                     if V(0) EQ -1 THEN  V=[GI] ELSE V=[GI,V] 
  222.                             Visited(GI)=-1
  223.                   ENDIF
  224.               ENDIF
  225.  
  226.              if Visited(Gap(i)) EQ 0 THEN PutV,Gap(i),V
  227.              Visited(Gap(i))=1
  228.              PutV,Here,V
  229.              END
  230.       ENDCASE
  231.     ENDELSE
  232.  ENDFOR
  233.  
  234.  
  235.  
  236.              
  237.   Visited(*)=0
  238.   Visited(0)=1
  239.   Wid = max(Sim1)
  240.   Str=Bytarr(10 + wid)
  241. printf,unit,Format='(40X,"Similarity")
  242. ;printf,unit,'          1___________________________________________________________________0'
  243. ST1 = bytarr(wid)
  244. ST1(0:wid-1) = BYTE("_")
  245. printf,unit,'         '+'1' + string(ST1) + '0'
  246.  
  247.   for i=1l,n DO BEGIN
  248.       printf,unit,Format='(A10,$)',CaseName(P(i-1))
  249.       Here=Imin(P(i-1))
  250.       S1=fix(Sim1(Here))
  251.       Str(0:S1)=Byte("-")
  252.       S=String(Str)
  253.       printf,unit,S
  254.       Str(0:S1)=Byte(" ")
  255.  
  256.      if(i NE n) THEN BEGIN
  257.  
  258.       if(Visited(Here) EQ 0)THEN BEGIN
  259.         Str(S1)=Byte("|")
  260.         Visited(Here)=1
  261.       ENDIF ELSE Str(S1)=Byte(" ")
  262.         S=String(str)  
  263.  
  264.        ;printf,unit,'          ',S
  265.  
  266.           
  267.       S2=fix(Sim1(Gap(i)))
  268.  
  269.        m=max(Str,gapStart)
  270.       if( gapStart+1 LE S2) THEN         $
  271.         Str(gapStart+1:S2)=Byte( "-")    $
  272.       else Str(S2:S2) = Byte( "-")
  273.       S=String(Str)
  274.  
  275.       printf,unit,'          ',S
  276.                                     
  277.      if ( gapStart+1 LE S2) THEN   $
  278.        Str(gapstart+1:S2)=Byte( " ")      $
  279.      else Str(S2:S2) = Byte(" ")
  280.  
  281.      if (Visited(Gap(i)) EQ 0) THEN BEGIN
  282.        Str(S2)=Byte("|")
  283.        Visited(Gap(i))=1
  284.      ENDIF ELSE Str(S2)=Byte(" ")
  285.       S=String(str)
  286.  
  287.  
  288.       ;printf,unit,'          ',S
  289.                             
  290.     ENDIF
  291.  ENDFOR
  292.  
  293.  
  294.  
  295.  
  296.   RETURN
  297.   END
  298.